#include <iostream>
#include <vector>
using namespace std;
void PrintArray(int *a, int n)
{
    for (int i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}
void InsertSort(int *a, int n)
{
    int i = 0;
    for (i = 0; i < n - 1; i++)
    {
        int end = i;
        int tmp = a[end + 1];
        while (end >= 0)
        {
            if (a[end] > tmp)
            {
                a[end + 1] = a[end];
                --end;
            }
            else
            {
                break;
            }
        }
        a[end + 1] = tmp;
    }
}
void ShellSort(int *a, int n)
{
    int gap = n;
    while (gap > 1)
    {
        gap = gap / 3 + 1;
        for (int i = 0; i < n - gap; i++)
        {
            int end = i;
            int tmp = a[end + gap];
            while (end >= 0)
            {
                if (a[end] > tmp)
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            a[end + gap] = tmp;
        }
        // PrintArray(a, n);
    }
}
void SelectSort(int *a, int n)
{
    int begin = 0;
    int end = n - 1;
    while (begin < end)
    {
        int mini = begin;
        int maxi = begin;
        for (int i = begin; i <= end; i++)
        {
            if (a[i] < a[mini])
            {
                mini = i;
            }
            if (a[i] > a[maxi])
            {
                maxi = i;
            }
        }
        swap(a[begin], a[mini]);
        if (begin == maxi)
        {
            maxi = mini;
        }
        swap(a[end], a[maxi]);
        ++begin;
        --end;
    }
}
void SelectSort1(int *a, int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        int mini = i;
        for (int j = i + 1; j < n; j++)
        {
            if (a[j] < a[mini])
            {
                mini = j;
            }
        }
        if (mini != i)
            swap(a[mini], a[i]);
    }
}
void AdJustDown(int *a, int n, int root)
{
    int parent = root;
    int child = 2 * parent + 1;
    while (child < n)
    {
        if (child + 1 < n && a[child + 1] > a[child])
        {
            ++child;
        }
        if (a[child] > a[parent])
        {
            swap(a[child], a[parent]);
            parent = child;
            child = 2 * parent + 1;
        }
        else
        {
            break;
        }
    }
}
void HeapSort(int *a, int n)
{
    for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    {
        AdJustDown(a, n, i);
    }
    int end = n - 1;
    while (end > 0)
    {
        swap(a[0], a[end]);
        AdJustDown(a, end, 0);
        --end;
    }
}
void PrintArray1(vector<int> &v)
{
    for (auto &e : v)
    {
        cout << e << " ";
    }
    cout << endl;
}
void BubbleSort(vector<int> &v)
{
    int n = v.size();
    for (int i = 0; i < n - 1; i++)
    {
        int flag = 1;
        for (int j = 0; j < n - i - 1; j++)
        {
            if (v[j] > v[j + 1])
            {
                flag = 0;
                swap(v[j], v[j + 1]);
            }
        }
        if (flag == 1)
        {
            break;
        }
    }
}
void BubbleSort1(vector<int> &v)
{
    int n = v.size();
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = 1; j < n - i; j++)
        {
            if (v[j - 1] > v[j])
            {
                swap(v[j - 1], v[j]);
            }
        }
    }
}
void BubbleSort2(vector<int> &v)
{
    int end = v.size();
    while (end > 0)
    {
        for (int i = 1; i < end; i++)
        {
            if (v[i - 1] > v[i])
            {
                swap(v[i - 1], v[i]);
            }
        }
        --end;
    }
}
int GetMidIndex(vector<int> &v, int begin, int end)
{
    int mid = (begin + end) >> 1;
    if (v[begin] < v[mid])
    {
        if (v[mid] < v[end])
        {
            return mid;
        }
        else if (v[begin] > v[end])
        {
            return begin;
        }
        else
        {
            return end;
        }
    }
    else
    {
        if (v[mid] > v[end])
        {
            return mid;
        }
        else if (v[begin] < v[end])
        {
            return begin;
        }
        else
        {
            return end;
        }
    }
}
// 左右指针法
int PartSort1(vector<int> &v, int begin, int end)
{
    int midindex = GetMidIndex(v, begin, end);
    swap(v[midindex], v[end]);
    int keyindex = end;
    while (begin < end)
    {
        while (begin < end && v[begin] <= v[keyindex]) //=必须有
            ++begin;
        while (begin < end && v[end] >= v[keyindex]) //=必须有
            --end;
        swap(v[begin], v[end]);
    }
    swap(v[begin], v[keyindex]);
    return begin;
}
void QuickSort1(vector<int> &v, int left, int right)
{
    if (left >= right)
        return;
    int div = PartSort1(v, left, right);
    QuickSort1(v, left, div - 1);
    QuickSort1(v, div + 1, right);
}